Present day computer networks today involve the interconnection of many types of digital modules which are required to communicate with each other both as a sender and a receiver.
A typical example of a complex network is shown in FIG. 2 where a system bus 10 connects a series of digital modules such as an A Series Central Processor (Unisys) Module 12, a Main Memory 14, a Processor Unit 18 such as an Intel (P6) Pentium or Pentium Pro. The system bus 10 is connected to system bus bridge units 22 and 24 which connect to other networks. Thus, bus 10b connects the system bus 10 to the I/O bus 20. The I/O bus 20 is here called a PCI bus. The PCI bus 20 connects another series of digital modules shown as an Input/Output Module 28, (IOM 2), an Auxiliary Message Arbitration Unit AMA 30, and another bridge unit 32 designated as PCI-EISA Bridge. The bridge unit 32 connects to a standard EISA bus 32e which connects to other EISA peripheral units designated 36.
In FIG. 2, the Input/Output Module, IOM 28, includes a group of digital modules designated as the Task Control Unit, TCU 42, Input/Output Unit IOU, 44, and Channel Manager Unit, CMU 46.
In the digital network shown in FIG. 2, it is necessary that a suitable protocol and proper control of message transfers be arranged for optimum operation of the system.
Present technology has made it possible to interconnect many digital modules such as processors, memories and Input/Output units in order to build powerful and effective computer systems. The performance of such multi-digital network systems depends on many factors such as the control of message flow, the scheduling and the interconnection methods used between the various digital modules, and also the implementation of fault free communication between modules.
One of the significant problems in message passing is the orderly and efficient transfer of messages from one digital module to another, and also the feature of message preservation when delivery of a message is not possible. Certain problematic conditions occur in networks which utilize both hardware modules and software modules. Basically, hardware modules when running uninterrupted work fast in handling and processing the data that is passed through them. On the other hand, software modules operating on a time-shared operating system are not completely dedicated to one type of operation, but are involved with task switching into different programs from time to time and thus, one earlier program may be delayed because the software is running on a second program and has not yet returned to the first program.
Thus, systems which used software solutions to try to handle the orderly transmission of messages ran into considerable difficulties. Some of these software solutions involved link lists in memory and assigned a number in memory to each message so that the messages would be accessed sequentially according to the number of the message. Then when that numbered message was used, the number was incremented and placed back in memory.
On these types of solutions using software, the queuing solution and the incrementing number solution leads to difficulties when you have multiple senders. Then it is necessary to make arrangements to see that the various sending modules are coordinated and not in conflict with each other. If a link list is built, it is not possible then to have two senders putting something into the list at the same time where they could interfere with each other.
Likewise, if there were two senders looking at a particular message number, the system would have to do something to prevent the senders from getting the same value of the number for their messages. Since there is a finite time from when the first sender gets the number, until he increments it and stores it back, then if the second sender asks for a number during that interval, the second sender is going to get the same number as the first sender and they both will put their messages in the same slot number. Thus, one sender will wipe out the message of the other sender.
It would be possible to prevent some of the software problems by having locking operations in memory, but again the problem with locking operations occurs when one software module obtains the lock which prevents other modules from doing anything until that module uses the lock, then the platform operating system takes the processor for some period of time causing every other sender to wait until a sender gets the processor back in order to do what is necessary to release the lock.
The present system provides a module which operates in a dedicated fashion as hardware to handle the message transmission control operations and the hardware responds rapidly and quickly since it does not have any need for a locking operation, because it is atomic, and because it guarantees that the two senders will not get the same number value. Thus, there is a fast certain and definite chronological system for message transfers that is done rapidly through hardware control modules, while at the same time it still can handle and be responsive to software modules operating in the system, thus allowing a mixture of hardware and software modules without the software modules slowing down the system.
General Overview:
One of the major features of the present system involves message order preservation, chronological sequences of message delivery and priorities whereby local messages, that is to say, messages from one processor to another, (where both processors are executing on the same computer system) are given higher priority than messages flowing from one computer system to another computer system.
The presently described system involves an Auxiliary Message Arbitrator Unit 30, AMA, which uses main system memory 14 to hold messages and utilizes an internal AMA board to provide the algorithmic control factors required. There is no need for any additional software tasks so that messages can flow between the sending and receiving units in a very direct and rapid fashion without any task switching overhead for software programs.
The Auxiliary Message Arbitrator 30 (FIG. 1A) of the present system can be used effectively in a classical network where there is one computer system consisting of multiple processors, all using one common memory subsystem. Quite contrarily, other prior art systems required specialized router node controllers and transposer modules for each node that was involved in sending and receiving messages.
U.S. Pat. No. 5,333,269 to Calvignac involved a mechanism for transferring messages between source and destination users through a shared memory. This patent involved a shared memory and control apparatus and provides data buffering and queuing of messages in transit between a sender and receiver. The messages are "chained" together to preserve their chronological order by small blocks of memory, each of which is associated with one buffer. The buffer control blocks also contain information about the buffer which they control. This system requires a control function that enqueues and dequeues messages in response to external requests. The present system described herein does not require the insertion of control information for messages, while additionally it also provides for notifying receivers of the presence of the message destined for the receiver.
The present Auxiliary Message Arbitrator System (AMA) provides a mechanism that allows a specific computer system to maintain a chronological ordering of messages that are being sent from a sending module to a receiving module. Usage is made of "tokens".
In the present system, a "token" is an 8-bit value that represents a physical slot (FIG. 1D) inside a message queue (dedicated to each module) which resides in the system memory 14. The available tokens reside in a Token RAM 58 (FIG. 1B) and each module is provided with up to 256 tokens which can indicate the 256 message slots for each dedicated message queue in the system memory 14 (FIG. 1D).
The present Auxiliary Message Arbitrator system allocates message queue slots to the senders and also notifies receivers which message in a queue is the next one to be examined.
In earlier systems, which used Unisys Corporation computer and network architecture, message passing was done between processors each of which had inbound message queues. Furthermore, these systems had "send-message" OP codes on their system busses and in their message address spaces. Messages were passed directly from sender to receiver with no memory queue accesses involved in the transfer.
The presently described network involves a platform which will simulate a personal computer PC-type of environment. The system has a system bus (System bus in FIG. 2) coupled to a I/O bus 20 (PCI BUS, FIG. 2). In this type of environment, there is no arrangement for "send message operations" or message address space to be utilized. Further, in the "lowest levels" of the system network configuration, there will not be any hard Input/Output Modules (IOMs) or Central Processing Modules (CPMs). The IOM and the CPM processors will be implemented in P6 code. Other configurations will actually have hardware IOMs and/or CPMs.
Thus as an example in FIG. 2, the CPM2, (16), and IOM 3, (17) are software emulated modules while CPM 1, (12), and IOM 2, (28), are hardware modules. The hardware modules are custom built for the system and are designed with inbound message queues, except that the system requires that all modules handle message queuing and de-queuing the same way. The system bus 10 (P6 bus) and the PCI BUS (I/O bus 20) only have memory access types of commands and the messages will be sent by means of those commands. The Intel P6 processor boards will be modules which are off-the-shelf, so there cannot be any inbound message queue on these boards. Further, all of the modules in the network must follow the same message protocol so that in this situation, the hardware modules cannot take advantage of inbound message queues.
In the present system network, a protocol has been developed for passing messages with memory access commands through the common system memory 14. The memory locations, called "slots," that the messages are passed to, are represented by "tokens" which are 8-bit data values that indicate which particular slot may be used for a particular message queue. Each receiving module in the system has at least one message queue dedicated to it.
When a system module must send a message, it first gets a token from a Token RAM 58 and then uses the Token to calculate the system memory address of where the message is located in system memory 14. The sending module then fills in the message at the designated slot of the message queue in system memory 14 and returns the token to the Token RAM when the message has been passed. The receiving module then gets "interrupted" to inform it that a message is residing in its dedicated message queue at a specific slot. The receiving module then gets the token which points to the slot of the message queue where, in system memory, the message resides. The message in system memory is then read out by the receiver, the token is returned to the Token RAM 58 and this frees up that particular message passing slot in system memory 14.
This particular protocol is facilitated by the Auxiliary Message Arbitrator 30 (AMA). This unit maintains these tokens and executes the message access commands in addition to initiating hard and soft Interrupts for hard and soft modules. It also supports the system timers. Physically, the AMA 30 resides in a PCI bus expansion slot.
In the present system a Get Message operation by a receiving module, must normally be preceded by an Interrupt to the message receiving module. However, when multiple messages are stacked in a message queue, a "Fast Empty" sequence can be initiated by the Auxiliary Message Arbitrator to enable the sending module to directly access each message in sequence on a series of Get Message operations without needing to use the intervening Interrupts between each Get Message operation, thus saving the time normally required for the intervening Interrupt cycles.